МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ Структура даних "Бінарне дерево пошуку" МЕТОДИЧНІ ВКАЗІВКИ до лабораторної роботи № 7 з дисципліни " Програмування. Частина III. Структури даних та алгоритми " для студентів напряму 6.050102 “Комп’ютерна інженерія” Львів – 2009 Методичні вказівки до лабораторної роботи "Структура даних "Бінарне дерево пошуку"" з дисципліни “Програмування. Частина IIІ. Структури даних та алгоритми" для підготовки студентів напрямку 6.0915 “Комп’ютерна інженерія” / Укл. Т.А.Лисак – Львів: Видавництво НУ “Львівська політехніка”, 2009 – 12 с. Укладач: Лисак Т.А., ст. викладач каф.ЕОМ Відповідальний за випуск: Мельник А.О., д-р техн. наук, проф. Рецензенти: Опир Ю.М., ст. викладач каф.ЕОМ Юрчак І.Ю., доцент кафедри САПР, к.т.н.  1. МЕТА РОБОТИ Вивчення абстрактної структури даних "Бінарне дерево пошуку". Набуття практичних навичок побудови дерева та використання його для розв'язання прикладних задач. 2. ПОРЯДОК ВИКОНАННЯ РОБОТИ 1. При підготовці до лабораторної роботи, необхідно засвоїти теоретичний матеріал по темі і підготуватись до контрольного опитування по розумінню питань даної тематики. 2. Згідно з індивідуальним завданням розробити алгоритм розв’язання задачі. 3. Підготувати програмну реалізацію розробленого алгоритму. Засобами вбудованого текстового редактора інтегрованого середовища набрати текст підготовленої програми. Відкомпілювати, налагодити та виконати програму. 4. Протестувати програму згідно зі складеною системою тестів і, при потребі, підкоректувати текст програми. Проаналізувати отримані результати. 5. Написати контрольне опитування по темі. 6. Оформити звіт по роботі. Без підготовкі до роботи (програмної реалізації розробленого алгоритму) студент до роботи не допускається. 3. ЗАВДАННЯ НА ЛАБОРАТОРНУ РОБОТУ Постановка задачі: Побудувати бінарне дерево пошуку для послідовності чисел, що вводяться з клавіатури. Виконати обхід дерева у заданому порядку та підрахувати: кількість вершин дерева при проходженні його у прямому порядку; кількість листків дерева при проходженні його у зворотньому порядку; кількість вузлів, що мають тільки одного нащадка при проходженні дерева у симетричному порядку. Виконати індивідуальне завдання згідно з варіантом. Варіанти завдань: Cтворити дзеркальне до заданого дерево. Вилучити з дерева всi листки. Вилучити з дерева всi вузли, що мають тільки одного безпосереднього нащадка. Вилучити з дерева всi вузли, що мають двох синів. Додати до дерева листки так, щоб воно стало строго бінарним деревом. Побудувати два бінарних дерева пошуку та визначити, чи є вони дзеркальним відображенням одне одного. Побудувати два бінарних дерева пошуку та визначити, чи можна одне дерево одержати з іншого шляхом вилучення однієї з його вершин. Знайти середнє арифметичне значення всіх вузлів дерева. Знайти середнє арифметичне значення всіх листків дерева. Добудувати дерево до строго бінарного дерева. Добудувати дерево до повного бінарного дерева. Визначити, чи побудоване дерево є строго бінарним деревом. Визначити, чи побудоване дерево є повним деревом. Визначити, чи заданий вузол дерева є коренем, або листком, або вершиною. Знайти найближчого спільного предка двох заданих вузлів дерева. Знайти рівень заданого вузла дерева. Знайти вузли, у яких кількість нащадків у лівому піддереві не дорівнює кількості нащадків у правому піддереві. Знайти вузли, для яких висота лівого поддерева не дорівнює висоті правого піддерева. Знайти довжину мінімального шляху між листами. Знайти максимальний шлях між вузлами дерева. 4. ВИБІР ІНДИВІДУАЛЬНОГО ЗАВДАННЯ № варіанта = [(день народження студента) * (місяць народження студента) ] % 20 + 1 5. ЗМІСТ ЗВІТУ I. Оформити титульну сторінку звіту стандартного зразка, на якій вказати назву лабораторної роботи, її номер та номер варіанту. II. В звіті мають бути відображені наступні пункти: 1. Мета роботи. 2. Постано...